1. Field of the Invention
The present invention relates to a system such as, for example, a sensor network, a mobile communication network, or a local area network (LAN) having a plurality of communicating nodes. More particularly, the invention relates to the avoidance of unwanted synchronization between nodes, and the avoidance of collisions between transmissions from different nodes.
2. Description of the Related Art
The nodes of concern in the present invention are intelligent devices such as computers, personal digital assistants (PDAs), mobile telephones, or so-called smart sensors, having computational capabilities as well as communication capabilities. Networks of such nodes have become widespread.
In a wireless network, since the nodes share a common communication medium, sometimes referred to as an air interface, they face a problem of collisions between transmissions from different nodes. Two well-known solutions to this problem are time division multiple access (TDMA), in which a central server assigns different time slots to the nodes, and carrier sense multiple access with collision avoidance (CSMA/CA), in which there is no central server but each node checks whether other nodes are transmitting before transmitting itself, detects collisions during transmission, and retransmits at a random time after a collision.
Wired networks such as local area networks may also have a common transmission medium such as a shared cable, with the attendant problem of collisions. The widely used Ethernet LAN communication system has adopted a solution known as carrier sense multiple access with collision detection (CSMA/CD), which is similar to CSMA/CA, except that collisions are detected from an increase in the direct-current component on the cable.
The above solutions are not entirely satisfactory. In the TDMA system, if the central server fails, all of the nodes under its control lose the capability to communicate. Furthermore, when nodes are added or removed, or when a node fails, runs out of power, or is moved to another location, the central server must discover the altered situation and reassign the time slots. This is generally a complex process, and is difficult to carry out rapidly when there are many nodes generating traffic at once. In the CSMA/CA and CSMA/CD systems, as the number of nodes generating traffic increases, so does the amount of overhead included in the traffic, causing an unavoidable loss of communication efficiency.
Transmission collisions, which occur when two nodes transmit simultaneously on the same communication medium, are just one example of the more general problem of unwanted synchronization between nodes. Another well-known example is the periodic transmission of routing information by routers in a network such as the Internet. Even though the router nodes are interconnected by separate cables, if they become synchronized and all transmit routing information at the same times, the network becomes overloaded at these times and communication may be delayed, or data may be lost. This type of synchronization has been shown to occur as an unwanted by-product of almost any type of interaction among nodes.